// https://leetcode.cn/problems/broken-calculator/description/

// 算法思路总结：
// 1. 逆向思维处理运算器损坏问题
// 2. 从目标值反向操作向起始值逼近
// 3. 当目标值大于起始值时：奇数次加1，偶数次除2
// 4. 当目标值小于等于起始值时：只能通过减1操作
// 5. 时间复杂度：O(logN)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int brokenCalc(int startValue, int target) 
    {
        if (startValue >= target) 
            return startValue - target;

        int ret = 0;
        while (target > startValue)
        {
            if (target & 1)
                target++;
            else
                target /= 2;
            ret++;
        }

        ret += startValue - target;

        return ret;
    }
};

int main()
{
    int s1 = 2, t1 = 3;
    int s2 = 5, t2 = 8;
    Solution sol;

    cout << sol.brokenCalc(s1, t1) << endl;
    cout << sol.brokenCalc(s2, t2) << endl;

    return 0;
}
